package org.xqh.study.leetcode.algorithm.median;

import com.alibaba.fastjson.JSON;
import org.xqh.utils.file.ReadTxtFileUtils;

import java.io.File;
import java.util.*;

/**
 * @ClassName MedianSlidingWindowSelf
 * @Description 滑动窗口中位数
 * @Author xuqianghui
 * @Date 2021/2/4 9:48
 * @Version 1.0
 */
public class MedianSlidingWindowSelf {

    public static void main(String[] args) {
//        int[] nums = {3,2,1,5,11,19,8,13,2,10,18,39,31,22,44,55,12,4};
        List<String> list = ReadTxtFileUtils.readTxt(new File("E:\\document\\yzs\\program\\leetcode\\滑动窗口优先队列.txt"));
//        List<String> d1 = JSONArray.parseArray(list.get(1), String.class);
//        List<String> d2 = JSONArray.parseArray(list.get(2), String.class);
//        for(int i = 0 ; i<d1.size(); i++){
//            if(!d1.get(i).equals(d2.get(i))){
//                System.out.println("序号: "+i+", 输出: "+d1.get(i)+", 答案: "+d2.get(i));
//            }
//        }

//        List<Integer> array = JSONArray.parseArray(list.get(0), Integer.class);
//        int[] nums = new int[array.size()];
//        for(int i = 0; i < nums.length; i ++){
//            nums[i] = array.get(i);
//        }
        int[] nums = {463179852, 462851407, 462242385, 474833169, 478446501, 479575244, 465645203};
        System.out.println(JSON.toJSONString(medianSlidingWindow(nums, 3)));
    }

    public static double[] medianSlidingWindow(int[] nums, int k) {
        int size = nums.length;
        StorePriorityQueue store = new StorePriorityQueue(k);
        for(int i = 0; i < k; i ++){
            store.insert(nums[i]);
        }
        int retLen = size - k + 1;
        double[] result = new double[retLen];
        for(int i = 0; i < retLen; i ++){
            if(i == 0){
                result[0] = store.getMedian();
            }else {
                store.insert(nums[i+k-1]);
                store.erase(nums[i-1]);//删除 左边元素
                result[i] = store.getMedian();
            }
        }
        return result;
    }

    public static class StorePriorityQueue{
        private PriorityQueue<Integer> small;//存放 小数据的优先队列
        private PriorityQueue<Integer> large;//存放大数据的 优先队列

        private int smallSize;//小队列 size
        private int largeSize;//大队列size
        private int k;//队列长度
        private Map<Integer, Integer> delMap;//延迟删除元素 标记 记录需要删除的次数

        public StorePriorityQueue(int k){
            this.small = new PriorityQueue<>(new Comparator<Integer>() {
                @Override
                public int compare(Integer num1, Integer num2) {
                    //堆顶 是大的 Integer
                    return num2.compareTo(num1);
                }
            });
            this.large = new PriorityQueue<>(new Comparator<Integer>() {
                @Override
                public int compare(Integer num1, Integer num2) {
                    return num1.compareTo(num2);
                }
            });
            this.smallSize = 0;
            this.largeSize = 0;
            this.k = k;
            delMap = new HashMap<>();
        }

        /**
         * 获取中位数
         * @return
         */
        public double getMedian(){
            return k % 2 == 0 ? ((double)small.peek() + large.peek())/2 : (double)small.peek();
        }

        /**
         * 插入数据
         * 如果 两个队列都为空 插入到 small
         * 如果 smallSize > largeSize + 1 插入到 large
         * @param num
         */
        public void insert(int num){
            if(small.isEmpty() || num <= small.peek()){
                small.offer(num);
                ++smallSize;
            }else {
                large.offer(num);
                ++largeSize;
            }
            makeBalance();
        }

        /**
         * 处理队列数据平衡
         */
        public void makeBalance(){
            if(smallSize > largeSize + 1){
                large.offer(small.poll());
                --smallSize;
                ++largeSize;
                //small堆顶元素 被移除
                prune(small);
            }else if(smallSize < largeSize) {
                small.offer(large.poll());
                ++smallSize;
                --largeSize;
                //large 堆顶元素被移除
                prune(large);
            }
        }

        /**
         * 清除 已被删除 元素(延迟删除)
         * @param queue
         */
        public void prune(PriorityQueue<Integer> queue){
            while (!queue.isEmpty()){
                Integer num = queue.peek();
                if(delMap.containsKey(num)){//堆顶元素 是需要删除的
                    queue.poll();//取出 被删除元素
                    delMap.put(num, delMap.get(num)-1);
                    if(delMap.get(num).intValue() == 0){
                        delMap.remove(num);
                    }
                }else {
                    break;
                }
            }
        }

        /**
         * 擦除 num 元素
         * @param num
         */
        public void erase(int num){
            delMap.put(num, delMap.getOrDefault(num, 0) + 1);
            if(num <= small.peek()){//对比 删除 元素 和 堆顶元素, 操作对应 队列长度
                --smallSize;
                if(num == small.peek()){
                    prune(small);
                }
            }else {
                --largeSize;
                if(num == large.peek()){
                    prune(large);
                }
            }
            makeBalance();
        }
    }
}
